﻿using System;

namespace 搜索插入位置
{
    class Program
    {   
        public int searchInsert(int[] nums, int target)
        {
            var last = nums.Length - 1;
            var first = 0;
            var mid = (first + last) / 2;
            if (target < nums[first] || target == nums[first]) return first;
            if (target == nums[last]) return last;
            if (target > nums[last]) return last + 1;
            do
            {
                mid = (first + last) / 2;
                if (nums[mid] == target || (target < nums[mid] && target > nums[mid - 1]))
                    return mid;
                if (target < nums[mid + 1] && target > nums[mid])
                    return mid + 1;
                int i = (nums[mid] > target) ? last = mid : first = mid;
            } while (first != last);
            return 0;
        }

        static void Main(string[] args)
        {
            Program program = new Program();
            //定义测试集
            int[] nums = new int[] { 1, 3, 5, 6 };
            Console.Write("插入位置的下标为：");
            Console.WriteLine(program.searchInsert(nums,5));
        }
    }
}
